package com.aqie.medium.greedy;

import java.util.*;

/**
 * 406  每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数
 * todo 涉及 ArrayList
 */
public class ReconstructQueue {
    /**
     * 1, 413ms
     * @param people
     * @return
     */
    public int[][] reconstructQueue(int[][] people) {
        if (people == null) return null;
        int[][] nums = new int[people.length][2];
        List<int[]> list = new ArrayList<>();
        // 将数组元素拷贝到 list
        Collections.addAll(list, people);

        list.sort((o1, o2) -> o1[0]==o2[0]?o1[1]-o2[1]:o2[0]-o1[0]);

        for (int i = 0; i < people.length; i++){
            int[] js = list.get(i);
            if (nums[js[1]] == null){
                nums[js[1]] = js;
            }else {
                for (int j = people.length - 1; j > js[1]; j--){
                    nums[j] = nums[j - 1];
                }
                nums[js[1]] = js;
            }
        }
        return nums;
    }

    /**
     * 2， 86ms
     * @param people
     * @return
     */
    public int[][] reconstructQueue2(int[][] people) {
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
        List<int[]> list = new LinkedList<>();
        for(int[] p : people) {
            list.add(p[1], p);
        }
        return list.toArray(new int[list.size()][]);
    }

    /**
     * 3, 20ms
     */
    class BitTree{
        private int[] tree;
        private int n ;
        BitTree(int n){
            tree = new int[n+1] ;
            this.n = n ;
        }

        public void add(int x,int add){
            while(x <= n){
                tree[x] += add ;
                x += (x&(-x)) ;
            }
        }

        public int getSum(int x){
            int sum = 0 ;
            while(x > 0){
                sum += tree[x] ;
                x -= (x&(-x)) ;
            }
            return sum ;
        }

    }

    public int[][] reconstructQueue3(int[][] people) {
        Arrays.sort(people,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                if(a[0] == b[0]){
                    return b[1] - a[1] ;
                }
                return a[0] - b[0] ;
            }
        }) ;
        int n = people.length ;
        BitTree tree = new BitTree(n) ;
        for(int i = 1;i <= n;i++){
            tree.add(i,1) ;
        }
        int[][] ans = new int[n][2] ;
        for(int i = 0;i < people.length;i++){
            int l = 1 ;
            int k = people[i][1] +1;
            int r = people.length ;
            while(l <= r){
                int mid = (l+r) >> 1 ;
                int sum = tree.getSum(mid) ;
                if(sum >= k){
                    r = mid-1 ;
                }else{
                    l = mid+1 ;
                }
            }
            tree.add(l,-1) ;
            ans[l-1] = people[i] ;
        }
        return ans ;
    }

    public static void main(String[] args) {
        Integer[][] people = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}};
        // int[] 转 Integer[]
        System.out.println(Arrays.deepToString(people));
        // 降序 返回负数
        Arrays.sort(people, new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] a, Integer[] b) {
                if (a[0] > b[0]) return -1;
                if (a[0].equals(b[0]) && a[1] < b[1]) return -1;
                return 1;

            }
        });
        // 排序后： [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
        System.out.println(Arrays.deepToString(people));
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>(6);
        for (Integer[] p : people){
            List<Integer> list = Arrays.asList(p);
            ArrayList<Integer> list2 = new ArrayList<>(list);
            ans.add(p[1], list2);
        }

        // 最终结果： [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
        System.out.println(ans);

        // Integer[] 转list

        int[] data = {2,3,1};
        // int[] 转 Integer[]
        Integer[] arr = Arrays.stream(data).boxed().toArray(Integer[]::new);
        // 默认由小到大
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        // a-b 升序  b-a 降序
        Arrays.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return b - a;
            }
        });
        System.out.println(Arrays.toString(arr));
    }
}
